package Map_Set;

public class MyHashBucket {
    //实现一个简单的哈希桶
    static class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    //哈希桶 是一个Node类型的数组
    private Node[] arr;
    public int usedSize;

    public MyHashBucket() {
        this.arr = new Node[10];
        this.usedSize=0;
    }

    //向哈希桶中插入 键值对
    public void put(int key,int val) {
        //1.确定下标
        int index=key % this.arr.length;

        //2.遍历 index下标 的链表
        Node cur=this.arr[index];
        //jdk1.8 使用的是 尾插法，判断条件应该是cur.next!=null
        //但我们现在尝试用 头插法
        while (cur!=null) {
            if (cur.key==key) {
                //更新val值
                cur.val=val;
            }
            cur=cur.next;
        }
        //3.插入
        //头插法
        Node node=new Node(key,val);
        node.next=arr[index];
        arr[index]=node;

        this.usedSize++;

        //4.判断 当前哈希桶有没有超过 负载因子,规定当负载因子超过0.75时，进行扩容
        if (loadFactor()>=0.75) {
            //扩容
            reSize();
        }

    }

    //计算负载因子，负载因子=当前存入表中的数据个数 / 表的长度
    public double loadFactor() {
        return  this.usedSize*1.0 / this.arr.length;
    }

    //扩容
    public void reSize() {
        //创建新数组
        Node[] newArray=new Node[this.arr.length*2];

        //遍历原来的哈希桶
        for (int i = 0; i <this.arr.length; i++) {
            Node cur=arr[i];

            //将原哈希桶的元素 重新哈希 放到新哈希桶
            while (cur!=null) {
                int index=cur.key % newArray.length;
                //将cur头插进 新数组的index下标
                Node curNext=cur.next;

                cur.next=newArray[index];
                newArray[index]=cur;
                cur=curNext;
            }
        }
        this.arr=newArray;
    }

    //从哈希桶中获取 值val
    public int get(int key) {
        int index=key % arr.length;//找到 key所对应的数组下标
        Node cur=arr[index];

        while (cur!=null) {
            if (cur.key==key) {
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;

    }


    public static void main(String[] args) {
        MyHashBucket hashBucket = new MyHashBucket();
        hashBucket.put(1,1);
        hashBucket.put(4,4);
        hashBucket.put(14,14);
        hashBucket.put(24,24);
        hashBucket.put(34,34);
        hashBucket.put(44,44);
        hashBucket.put(54,54);
        hashBucket.put(64,64);//负载因子 > 0.75,会扩容


        System.out.println();

    }
}
